
map_width	equ	32	; must be strictly smaller than 128
map_height	equ	24
map_size	equ	map_width * map_height
max_steps	equ	253	; must be odd (or else change Z/NZ condition below)
					; must be <= 253
min			equ	24	; min(map_width, map_height, max_steps)

;++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

; Calculate distance to all reachable cells from the given start cell (or
; up to 'max_step' steps removed from the start cell).
; 
; In: D,E = x,y-coordinates of start position
;     map-array: walls should have the value 0
;                empty cells should have the value 255
;
; Out: pmap-array is filled in:
;  - walls cells have value 0
;  - unreachable cells (or not reached within 'max_steps') have value 255
;  - the start cell is given the value '254-max_steps'
;  - other cells are given an increasingly bigger value depending
;    on the number of steps required to reach this cell
;   (So start and reachable cells are given values in range [1..254])

psect    text,class=CODE
	global _calc_distance

_calc_distance:	
		; Copy map to helper map. Initially no cell is marked as
		; reachable (they all have value=255). Except for walls,
		; those have value=0.
		; An alternative is to work on the original map, and reset
		; all values!=0 back to 255 when a new distance-map needs
		; to be calculated.

		exx
		ld	hl,map
		ld	de,pmap
		ld	bc,map_size
		ldir

		exx			; d,e = x,y-coord of start position
		ld	l,e		; can be removed if D,E input is swapped
		ld	h,0		; hl = y-coord
		ld	e,d
		ld	d,h		; de = x-coord
		add	hl,hl		; *2
		add	hl,hl		; *4
		add	hl,hl		; *8
		add	hl,hl		; *16
		add	hl,hl		; *32   depends on map_width!!
		add	hl,de
		ld	de,pmap
		add	hl,de		; address of the start cell in pmap

		di
		ld	(save_sp),sp	; after this point we can't use 'normal'
		ld	sp,worklist1+2	;   stack operations anymore
		xor	a
		ld	(worklist1+3),a	; mark end of list
		ld	de,worklist2

		ld	a,255-max_steps		; step-counter, starts at 2 instead of 1!!
		ld	(hl),254-max_steps 	; mark start cell

		; At this point
		;  A  = step-count = 2
		;  HL = address of start cell
		;  SP = address of next item in worklist1 (points to 0-byte
		;       because the initial list only contains the start cell
		;       and as an optimization we don't explicitly store that
		;	cell in the list)
		;  DE = worklist2 (newly reached cells will be stored here)
		;  BC not in use

step_loop:	
		; at this point:
		;  SP = address of next item in worklist
		;  HL = address of current cell
		dec	hl		; left neighbor cell
		cp	(hl)		; (HL) <= A means:    (so not-carry)
		jr	nc,skip_left	;  -> already marked or a wall
		; new cell is reached, mark it and store it in the new worklist
		ld	(hl),a		; mark cell with step-counter
		ex	de,hl
		ld	(hl),e
		inc	hl
		ld	(hl),d		; store cell in new worklist
		inc	hl		; update to next free position in list
		ex	de,hl
skip_left:
		inc	hl
		inc	hl		; right neighbor
		cp	(hl)
		jr	nc,skip_right
		ld	(hl),a
		ex	de,hl
		ld	(hl),e
		inc	hl
		ld	(hl),d
		inc	hl
		ex	de,hl
skip_right:
		ld	bc,-map_width-1
		add	hl,bc		; up neighbor
		cp	(hl)
		jr	nc,skip_up
		ld	(hl),a
		ex	de,hl
		ld	(hl),e
		inc	hl
		ld	(hl),d
		inc	hl
		ex	de,hl
skip_up:
		ld	bc,map_width*2	; if (map_width < 128) -> B=0, see below
		add	hl,bc		; down neighbor
		cp	(hl)
		jr	nc,skip_down
		ld	(hl),a
		ex	de,hl
		ld	(hl),e
		inc	hl
		ld	(hl),d
		inc	hl
		ex	de,hl
skip_down:
		pop	hl		; hl = next item from worklist
		inc	h
		dec	h		; upper-byte != 0
		jr	nz,step_loop	;  -> end-of-list not yet reached

		ex	de,hl
		inc	hl
		ld	(hl),b		; mark end of next worklist (B=0)

		inc	a		; increase step count
		ld	de,worklist2
		ld	hl,worklist1
		bit	0,a
		jr	z,swap_lists	; Z/NZ depends on the initial step-count!
		ex	de,hl		; swap lists (depends on odd/even step count)
swap_lists:
		ld	sp,hl

		; at this point:
		;  SP = address of first item in the new worklist
		;  DE = address of next worklist (this list does not need to cleared)
		;  A  = step count
		pop	hl
		inc	h
		dec	h		; h == 0?
		jr	nz,step_loop

		; We've just switched to a new worklist, and we're already
		; at the end of that list (so list was empty). This means
		; that all reachable cells have been marked.
		ld	sp,(save_sp)	; restore stack pointer
		ei
		ret

;++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 psect    data,class=DATA

W		equ	0	; wall
.		equ	255	; empty space

		global _cmap,_map,_worldMap
_map:
map:		ds	map_size
_cmap:	
pmap:		ds	map_size

_worldMap:	ds	map_size

worklist1:	ds	2*4*min
worklist2:	ds	2*4*min
save_sp:	ds	2

